package monotoneStack;

import java.util.*;

/**
 * 单调栈
 */
public class Solution {

    /**
     * 84. 柱状图中最大的矩形
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] newHeight = new int[n + 2];
        System.arraycopy(heights, 0, newHeight, 1, n);
        Stack<Integer> stack = new Stack<>();
        int result = 0;
        for (int i = 0; i < newHeight.length; i++) {
            while(!stack.isEmpty() && newHeight[i] < newHeight[stack.peek()]){
                int height = newHeight[stack.pop()];
                int width = i - stack.peek() - 1;
                result = Math.max(result, height * width);
            }
            stack.push(i);
        }
        return result;
    }

    /**
     * 42. 接雨水
     * @param height
     * @return
     */
    public int trap(int[] height) {
        int result = 0;
        Stack<Integer> stack = new Stack<>();
        int n = height.length;

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();
                int currWidth = i - left - 1;
                int currHeight = Math.min(height[left], height[i]) - height[top];
                result += currWidth * currHeight;
            }
            stack.push(i);
        }

        return result;
    }

    /**
     * 739. 每日温度
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int n = temperatures.length;
        int[] result = new int[n];

        for (int i = 0; i < n; i++) {
            while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int before = stack.pop();
                result[before] = i - before;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()) {
            result[stack.pop()] = 0;
        }
        return result;
    }

    /**
     * 316. 去除重复字母
     * @param s
     * @return
     */
    public String removeDuplicateLetters(String s) {
        int n = s.length();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(s.charAt(i), i);
        }
        Stack<Character> stack = new Stack<>();
        Set<Character> set = new HashSet<>();
        StringBuilder stringBuilder = new StringBuilder();

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (!set.contains(ch)) {
                while(!stack.isEmpty() && map.get(stack.peek()) > i && stack.peek() > ch) {
                    set.remove(stack.peek());
                    stack.pop();
                }
                stack.push(ch);
                set.add(ch);
            }
        }
        for (int i = 0; i < stack.size(); i++) {
            stringBuilder.append(stack.get(i));
        }
        return stringBuilder.toString();
    }
}
